{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #破解闯关密码"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #string #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #字符串 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: crackPassword"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #破解闯关密码"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>闯关游戏需要破解一组密码，闯关组给出的有关密码的线索是：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>一个拥有密码所有元素的非负整数数组 <code>password</code></li>\n",
    "\t<li>密码是 <code>password</code> 中所有元素拼接后得到的最小的一个数</li>\n",
    "</ul>\n",
    "\n",
    "<p>请编写一个程序返回这个密码。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>password = [15, 8, 7]\n",
    "<strong>输出: </strong>\"1578\"</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>password = [0, 3, 30, 34, 5, 9]\n",
    "<strong>输出: </strong>\"03033459\"</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt; password.length &lt;= 100</code></li>\n",
    "</ul>\n",
    "\n",
    "<p><strong>说明: </strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>输出结果可能非常大，所以你需要返回一个字符串而不是整数</li>\n",
    "\t<li>拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof](https://leetcode.cn/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof](https://leetcode.cn/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        strs = [str(i) for i in password]\n",
    "        left = 0\n",
    "        right = len(password)-1\n",
    "        def quick_sort(i, j):\n",
    "            if i+j<=j+i:\n",
    "                return -1\n",
    "            else:\n",
    "                return 1\n",
    "        strs.sort(key=functools.cmp_to_key(quick_sort))\n",
    "\n",
    "        return ''.join(strs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        def islesser(a, b):\n",
    "            a, b = str(a), str(b)\n",
    "            return a+b < b+a\n",
    "        for i in range(len(password)-1):\n",
    "            flag = False\n",
    "            for j in range(len(password)-1-i):\n",
    "                if islesser(password[j+1], password[j]):\n",
    "                    password[j+1], password[j] = password[j], password[j+1]\n",
    "                    flag = True\n",
    "            if not flag:\n",
    "                break\n",
    "        return ''.join(list(map(str, password)))\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        def rule(x,y):\n",
    "            a , b = x + y,y + x\n",
    "            if a > b:\n",
    "                return 1\n",
    "            elif a < b:\n",
    "                return -1\n",
    "            else:\n",
    "                return 0\n",
    "\n",
    "        password = [str(p) for p in password] \n",
    "        password.sort(key = functools.cmp_to_key(rule))\n",
    "        return \"\".join(password)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        password = [str(i) for i in password]\n",
    "        password.sort(key=functools.cmp_to_key(self.shuzhi))\n",
    "        return ''.join(password)\n",
    "    def shuzhi(self, x, y):\n",
    "        if x + y > y + x:\n",
    "            return 1\n",
    "        elif x + y < y + x:\n",
    "            return -1\n",
    "        else:\n",
    "            return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        def cp(n1, n2):\n",
    "            if int(n1 + n2) > int(n2 + n1):\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        \n",
    "        nums = password\n",
    "        nums = [str(num) for num in nums]\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i, len(nums)):\n",
    "                if cp(nums[i], nums[j]):\n",
    "                    nums[i], nums[j] = nums[j], nums[i]\n",
    "        \n",
    "        return ''.join(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password: list[int]) -> str:\n",
    "        def sort_rule(x,y):\n",
    "            a,b = x+y,y+x\n",
    "            if a>b:return 1\n",
    "            elif a<b:return -1\n",
    "            else:return 0\n",
    "        ans = [str(password[i]) for i in range(len(password))]\n",
    "        ans.sort(key = functools.cmp_to_key(sort_rule))\n",
    "        return \"\".join(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        str_ = [str(ele) for ele in password]\n",
    "        n = len(password)\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                if str_[i] + str_[j] > str_[j] + str_[i]:\n",
    "                    str_[i], str_[j] = str_[j], str_[i]\n",
    "        return \"\".join(str_)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        # 按字符串顺序排序：但对 3、30、34 这种情况处理有问题！30334，而非 33034\n",
    "        # password.sort(key = lambda x:str(x))\n",
    "        # return \"\".join([str(x) for x in password])\n",
    "\n",
    "        def sort_rule(x, y):\n",
    "            a, b = x + y, y + x\n",
    "            if a > b: return 1\n",
    "            elif a < b: return -1\n",
    "            else: return 0\n",
    "        \n",
    "        strs = [str(num) for num in password]\n",
    "        # 可实现通用的排序操作：!!!\n",
    "        strs.sort(key = functools.cmp_to_key(sort_rule))\n",
    "        return ''.join(strs)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, nums: List[int]) -> str:\n",
    "        # 定义一个比较函数 cmp，用于比较两个数字的组合大小\n",
    "        def cmp(a, b):\n",
    "            # 将 a 和 b 拼接成字符串 x 和 y\n",
    "            x, y = a + b, b + a\n",
    "            # 比较 x 和 y 的大小\n",
    "            return -1 if x < y else 1\n",
    "\n",
    "        # 将 nums 中的数字转换为字符串，并存储在 ans 列表中\n",
    "        ans = [str(x) for x in nums]\n",
    "        # 使用自定义的比较函数 cmp 来对 ans 列表进行排序\n",
    "        ans.sort(key=cmp_to_key(cmp))\n",
    "        # 将排序后的 ans 列表中的字符串连接成一个整体作为结果\n",
    "        return \"\".join(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password: list[int]) -> str:\n",
    "\n",
    "        ans = [str(password[i]) for i in range(len(password))]\n",
    "        ans.sort()\n",
    "        ans2 = deepcopy(ans)\n",
    "        for i in range(1,len(ans)):\n",
    "            if ans[i-1]+ans[i]>ans[i]+ans[i-1]:\n",
    "                temp = ans[i-1]\n",
    "                ans[i-1] = ans[i]\n",
    "                ans[i] = temp\n",
    "        while ans2 != ans:\n",
    "            ans2 = deepcopy(ans)\n",
    "            for i in range(1,len(ans)):\n",
    "                if ans[i-1]+ans[i]>ans[i]+ans[i-1]:\n",
    "                    temp = ans[i-1]\n",
    "                    ans[i-1] = ans[i]\n",
    "                    ans[i] = temp\n",
    "        return \"\".join(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        def order(a,b):\n",
    "            if a + b > b + a:\n",
    "                return True\n",
    "            else: \n",
    "                return False\n",
    "        nums= [str(i) for i in password]\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(0,len(nums)-i-1):\n",
    "                if order(nums[j], nums[j+1]):\n",
    "                    nums[j], nums[j+1] = nums[j+1], nums[j] \n",
    "        return \"\".join(nums)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        def cmp(a: int, b: int) -> int:\n",
    "            if a + b > b + a:\n",
    "                return 1\n",
    "            if a + b < b + a:\n",
    "                return -1\n",
    "            if a + b == b + a:\n",
    "                return 0\n",
    "\n",
    "        from functools import cmp_to_key\n",
    "        nums_str = list(map(str, password))\n",
    "        nums_str.sort(key=cmp_to_key(cmp))\n",
    "        return \"\".join(nums_str)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        if not password:\n",
    "            return \"\"\n",
    "\n",
    "        # 将密码数组转换为字符串数组，以便进行排序\n",
    "        password_str = [str(num) for num in password]\n",
    "\n",
    "        n = len(password_str)\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(0, n-i-1):\n",
    "                if password_str[j] + password_str[j+1] > password_str[j+1] + password_str[j]:\n",
    "                    # 交换位置\n",
    "                    password_str[j], password_str[j+1] = password_str[j+1], password_str[j]\n",
    "        \n",
    "        return ''.join(password_str)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        def cmp(a, b):\n",
    "            if a + b > b + a:\n",
    "                return 1\n",
    "            elif a + b == b + a:\n",
    "                return 0\n",
    "            else:\n",
    "                return -1\n",
    "\n",
    "        nums = list(map(str, password))\n",
    "        nums.sort(key=functools.cmp_to_key(cmp))\n",
    "        return ''.join(nums)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def swap(self, nums, i, j):\n",
    "            nums[i], nums[j] = nums[j], nums[i]\n",
    "    def partition(self, nums, L, R):\n",
    "        i = L + random.randint(0,(R-L))\n",
    "        self.swap(nums,i,R)\n",
    "        pivot = nums[R]\n",
    "        left = L - 1\n",
    "        right = R\n",
    "        while L < right:\n",
    "            if nums[L] + pivot < pivot + nums[L]:\n",
    "                left += 1\n",
    "                self.swap(nums,L,left)\n",
    "                L += 1\n",
    "            elif nums[L] + pivot > pivot + nums[L]:\n",
    "                right -= 1\n",
    "                self.swap(nums,L,right)\n",
    "            else:\n",
    "                L += 1\n",
    "        self.swap(nums,right, R)\n",
    "        return [left + 1, right]\n",
    "    def quickSort(self, nums, L, R):\n",
    "        if L < R:\n",
    "            pos = self.partition(nums,L, R)\n",
    "            self.quickSort(nums,L,pos[0] - 1)\n",
    "            self.quickSort(nums,pos[1] + 1, R)\n",
    "\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        if not password:\n",
    "            return \"\"\n",
    "        password = [str(x) for x in password]\n",
    "        self.quickSort(password, 0 , len(password) - 1)\n",
    "        return \"\".join(password)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        from functools import cmp_to_key\n",
    "\n",
    "        num_str = [str(x) for x in password]\n",
    "        def compare(a, b):\n",
    "            x, y = a+b, b+a\n",
    "            if x > y:\n",
    "                return 1\n",
    "            elif x < y:\n",
    "                return -1\n",
    "            else: return 0\n",
    "        \n",
    "        num_str.sort(key=cmp_to_key(compare))\n",
    "        return ''.join(num_str)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        password = list(map(str,password))\n",
    "        l = len(password) - 1\n",
    "\n",
    "        for i in range(l):\n",
    "            for j in range(l-i):\n",
    "                if password[j] + password[j+1] >= password[j+1] + password[j]:\n",
    "                    password[j],password[j+1] = password[j+1],password[j]\n",
    "\n",
    "        return \"\".join(password)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        # Convert all numbers to strings for easier manipulation\n",
    "        password = list(map(str, password))\n",
    "        \n",
    "        # Define a custom comparator for sorting\n",
    "        def compare(x, y):\n",
    "            if x + y < y + x:\n",
    "                return -1\n",
    "            elif x + y == y + x:\n",
    "                return 0\n",
    "            else:\n",
    "                return 1\n",
    "        \n",
    "        # Sort the list with the custom comparator\n",
    "        password.sort(key = cmp_to_key(compare))\n",
    "        \n",
    "        # Join all elements to get the smallest number\n",
    "        result = ''.join(password)\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        # 冒泡排序，每两个数组合要是最小的，如何大了就换顺序\n",
    "        n = len(password)\n",
    "        for i in range(n - 1):\n",
    "            for j in range(n - i - 1):\n",
    "                if int(str(password[j]) + str(password[j+1])) > int(str(password[j+1]) + str(password[j])):\n",
    "                    password[j], password[j+1] = password[j+1], password[j]\n",
    "                #print(i, j, password)\n",
    "\n",
    "\n",
    "        return \"\".join(list(map(lambda x:str(x), password)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        def cmp(x,y):\n",
    "            if x+y > y+x:\n",
    "                return 1\n",
    "            elif x+y < y+x:\n",
    "                return -1\n",
    "            else: return 0\n",
    "        l = list(map(str,password))\n",
    "        l = sorted(l,key=functools.cmp_to_key(cmp))\n",
    "        s = ''.join(l)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def single_digit_res(self, password):\n",
    "        max_len = 0\n",
    "        for each in password:\n",
    "            if len(each) > max_len:\n",
    "                max_len = len(each)\n",
    "        cut_list = []\n",
    "        for i in range(len(password)):\n",
    "            if len(password[i]) < max_len:\n",
    "                cut_list.append(len(password[i]))\n",
    "                password[i] += password[i][0] * (max_len-len(password[i]))\n",
    "            else:\n",
    "                cut_list.append(len(password[i]))\n",
    "        for i in range(len(password)-1):\n",
    "            for j in range(i + 1, len(password)):\n",
    "                if password[i] > password[j]:\n",
    "                    password[i], password[j] = password[j], password[i]\n",
    "                    cut_list[i], cut_list[j] = cut_list[j], cut_list[i]\n",
    "                elif password[i] == password[j]:\n",
    "                    if password[i][cut_list[i]-1] > password[i][0]:\n",
    "                        password[i], password[j] = password[j], password[i]\n",
    "                        cut_list[i], cut_list[j] = cut_list[j], cut_list[i]\n",
    "\n",
    "        return \"\".join([password[i][:cut_list[i]] for i in range(len(password))])\n",
    "\n",
    "\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        res = \"\"\n",
    "        password = [str(each) for each in password]\n",
    "        for i in range(10):\n",
    "            tmp = [each for each in password if each[0] == str(i)]\n",
    "            res += self.single_digit_res(tmp)\n",
    "        return res\n",
    "        \n",
    "# class Solution:\n",
    "#     def crackPassword(self, password: List[int]) -> str:\n",
    "#         def sort_rule(x, y):\n",
    "#             a, b = x + y, y + x\n",
    "#             if a > b: return 1\n",
    "#             elif a < b: return -1\n",
    "#             else: return 0\n",
    "        \n",
    "#         strs = [str(num) for num in password]\n",
    "#         strs.sort(key = functools.cmp_to_key(sort_rule))\n",
    "#         return ''.join(strs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def switch(self, a: int, b: int) -> bool:\n",
    "        str_a, str_b = str(a), str(b)\n",
    "        return True if int(str_a + str_b) > int(str_b + str_a) else False\n",
    "        # if a == 0 or (a == 100 and b != 0):\n",
    "        #     return False\n",
    "        # if b == 0 or b == 100:\n",
    "        #     return True\n",
    "        # if (a >= 10 and b >= 10) or (a < 10 and b < 10):\n",
    "        #     return True if a > b else False\n",
    "        # elif a >= 10:\n",
    "        #     a_10, a_1 = a // 10, a % 10\n",
    "        #     return True if a_10 > b or (a_10 == b and a_1 >= a_10) else False\n",
    "        # elif b >= 10:\n",
    "        #     b_10, b_1 = b // 10, b % 10\n",
    "        #     return False if b_10 > a or (b_10 == a and b_1 >= b_10) else True\n",
    "\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        l = len(password)\n",
    "        while l > 1:\n",
    "            for i in range(l-1):\n",
    "                if self.switch(password[i], password[i+1]):\n",
    "                    password[i], password[i+1] = password[i+1], password[i]\n",
    "            l -= 1\n",
    "        res = ''\n",
    "        for num in password:\n",
    "            res += str(num)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        n = len(password)\n",
    "        strs = [str(num) for num in password]\n",
    "\n",
    "        def compare(s1: str, s2: str) -> int:\n",
    "            # 看看那种拼接方式得到的数字更小，排前面\n",
    "            # 不用转成 int 类型，因为字符串的比较算法和正整数的比较算法是一样的\n",
    "            # 而且拼接字符串比较长，会导致 int 类型溢出\n",
    "            return -1 if s1 + s2 < s2 + s1 else 1\n",
    "\n",
    "        strs.sort(key=functools.cmp_to_key(compare))\n",
    "\n",
    "        return ''.join(strs)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        def cmp(a1, a2):\n",
    "            x = a1 + a2\n",
    "            y = a2 + a1\n",
    "            if x > y: \n",
    "                return 1\n",
    "            elif x < y: \n",
    "                return -1\n",
    "            else: \n",
    "                return 0\n",
    "\n",
    "\n",
    "        password = list(map(str,password))\n",
    "        ans = sorted(password, key = functools.cmp_to_key(cmp))\n",
    "        return \"\".join(ans)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        def cmp(a,b):\n",
    "            if a+b < b+a:return -1\n",
    "            elif a+b > b+a:return 1\n",
    "            else:return 0\n",
    "\n",
    "        password = list(map(str,password))\n",
    "        ans = sorted(password, key = functools.cmp_to_key(cmp))\n",
    "        return \"\".join(ans)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        def cmp(a:str, b:str) -> int:\n",
    "            if a+b == b+a:\n",
    "                return 0\n",
    "            elif a+b > b+a:\n",
    "                return 1\n",
    "            else:\n",
    "                return -1\n",
    "        nums = list(map(str, password))\n",
    "        nums.sort(key=functools.cmp_to_key(cmp))\n",
    "        return ''.join(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        def sort_rule(x, y):\n",
    "            a, b = x + y, y + x\n",
    "            if a > b: return 1\n",
    "            elif a < b: return -1\n",
    "            else: return 0\n",
    "\n",
    "        strs = [str(num) for num in password]\n",
    "        strs.sort(key = functools.cmp_to_key(sort_rule))\n",
    "        return ''.join(strs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        def compare(a, b):\n",
    "            if a + b > b + a:\n",
    "                return 1\n",
    "            elif a + b < b + a:\n",
    "                return -1\n",
    "            return 0\n",
    "        n = len(password)\n",
    "        for i in range(n):\n",
    "            password[i] = str(password[i])\n",
    "        password.sort(key=cmp_to_key(compare))\n",
    "        return ''.join(password)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        def sort_rule(x, y):\n",
    "            a, b = x + y, y + x\n",
    "            if a > b :\n",
    "                return 1\n",
    "            elif a < b :\n",
    "                return -1\n",
    "            else :\n",
    "                return 0\n",
    "\n",
    "        strs = [str(num) for num in password]\n",
    "        strs.sort(key = functools.cmp_to_key(sort_rule))\n",
    "        return ''.join(strs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "\n",
    "        def quick_sort(nums, low, high):\n",
    "            if low < high:\n",
    "                pivot = nums[high]\n",
    "                pivot_str = str(pivot)\n",
    "                i = low - 1\n",
    "                for j in range(low, high):\n",
    "                    if int(str(nums[j]) + pivot_str) < int(pivot_str + str(nums[j])):\n",
    "                        i += 1\n",
    "                        nums[i], nums[j] = nums[j], nums[i]\n",
    "                pivot_index = i + 1\n",
    "                nums[pivot_index], nums[high] = nums[high], nums[pivot_index]\n",
    "                quick_sort(nums, low, pivot_index - 1)\n",
    "                quick_sort(nums, pivot_index + 1, high)\n",
    "        quick_sort(password, 0, len(password) - 1)\n",
    "        return \"\".join([str(p) for p in password])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        def sort_rule(x, y):\n",
    "            a, b = x + y, y + x\n",
    "            if a > b: return 1\n",
    "            elif a < b: return -1\n",
    "            else: return 0\n",
    "        \n",
    "        strs = [str(num) for num in password]\n",
    "        strs.sort(key = functools.cmp_to_key(sort_rule))\n",
    "        return ''.join(strs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        n = len(password)\n",
    "        password_new = [str(i) for i in password]\n",
    "        for i in range(n):\n",
    "            for j in range(i,n):\n",
    "                if password_new[i]+password_new[j] > password_new[j]+password_new[i]:\n",
    "                    password_new[i], password_new[j] = password_new[j], password_new[i]\n",
    "        # print(password_new)\n",
    "        return \"\".join(password_new)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        n = len(password)\n",
    "        password_new = [str(i) for i in password]\n",
    "        # password_new = [i for i in password]\n",
    "        for i in range(n):\n",
    "            for j in range(i,n):\n",
    "                if password_new[i]+password_new[j] > password_new[j]+password_new[i]:\n",
    "                    password_new[i], password_new[j] = password_new[j], password_new[i]\n",
    "        # print(password_new)\n",
    "        return \"\".join(password_new)\n",
    "\n",
    "    def crackPassword_old(self, password: List[int]) -> str:\n",
    "        def quick_sort(l, r):\n",
    "            if l >= r:\n",
    "                return\n",
    "            i, j = l, r\n",
    "            while i < j:\n",
    "                while strs[j] + strs[l] >= strs[l] + strs[j] and i < j:\n",
    "                    j -= 1\n",
    "                while strs[i] + strs[l] <= strs[l] + strs[i] and i < j:\n",
    "                    i += 1\n",
    "                strs[i], strs[j] = strs[j], strs[i]\n",
    "\n",
    "            strs[i], strs[l] = strs[l], strs[i]\n",
    "            quick_sort(l, i - 1)\n",
    "            quick_sort(i + 1, r)\n",
    "        strs = [str(num) for num in password]\n",
    "        quick_sort(0, len(strs) - 1)\n",
    "        # print(strs)\n",
    "        return \"\".join(strs)\n",
    "# class Solution:\n",
    "#     def crackPassword(self, password: List[int]) -> str:\n",
    "#         def quick_sort(l, r):\n",
    "#             if l >= r:\n",
    "#                 return\n",
    "#             i, j = l, r\n",
    "#             while i < j:\n",
    "#                 while strs[j] + strs[l] >= strs[l] + strs[j] and i < j:\n",
    "#                     j -= 1\n",
    "#                 while strs[i] + strs[l] <= strs[l] + strs[i] and i < j:\n",
    "#                     i += 1\n",
    "#                 strs[i], strs[j] = strs[j], strs[i]\n",
    "#             strs[i], strs[l] = strs[l], strs[i]\n",
    "#             quick_sort(l, i - 1)\n",
    "#             quick_sort(i + 1, r)\n",
    "#\n",
    "#         strs = [str(num) for num in password]\n",
    "#         quick_sort(0, len(strs) - 1)\n",
    "#         return ''.join(strs)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        # Convert all numbers to strings for easier manipulation\n",
    "        password = list(map(str, password))\n",
    "        \n",
    "        # Sort the list with a custom comparator\n",
    "        # The comparator defines the order based on concatenation of pairs\n",
    "        password.sort(key = lambda x: x * 10)\n",
    "        \n",
    "        # Join all elements to get the smallest number\n",
    "        return ''.join(password)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        def comparator(a: int, b: int):\n",
    "            if str(a) + str(b) > str(b) + str(a):\n",
    "                return 1\n",
    "            elif str(a) + str(b) < str(b) + str(a):\n",
    "                return -1\n",
    "            else:\n",
    "                return 0\n",
    "\n",
    "        def quick_sort(arr: list[int], l: int, r: int):\n",
    "            if l >= r:\n",
    "                return\n",
    "            i, j = l, r\n",
    "            while i < j:\n",
    "                while i < j and comparator(arr[j], arr[l]) >= 0:\n",
    "                    j -= 1\n",
    "                while i < j and comparator(arr[i], arr[l]) <= 0:\n",
    "                    i += 1\n",
    "                arr[i], arr[j] = arr[j], arr[i]\n",
    "            arr[l], arr[i] = arr[i], arr[l]\n",
    "\n",
    "            quick_sort(arr, l, i - 1)\n",
    "            quick_sort(arr, i + 1, r)\n",
    "\n",
    "        quick_sort(password, 0, len(password) - 1)\n",
    "        return \"\".join([str(_) for _ in password])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        def cmp(a:str, b:str) -> int:\n",
    "            if a+b == b+a:\n",
    "                return 0\n",
    "            elif a+b > b+a:\n",
    "                return 1\n",
    "            else:\n",
    "                return -1\n",
    "        nums = list(map(str, password))\n",
    "        nums.sort(key=functools.cmp_to_key(cmp))\n",
    "        return ''.join(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        from functools import cmp_to_key\n",
    "        def my_cmp(x,y):\n",
    "            x1 = str(x)+str(y)\n",
    "            x2 = str(y)+str(x)\n",
    "            if int(x1)>int(x2):\n",
    "                return 1\n",
    "            else:\n",
    "                return -1\n",
    "        \n",
    "        sorted_password = sorted(password,key=cmp_to_key(my_cmp))\n",
    "        return \"\".join([str(v) for v in sorted_password])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cmp_to_key\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        strs = [str(i) for i in password]\n",
    "        key = cmp_to_key(lambda x,y: int(x+y)-int(y+x))\n",
    "\n",
    "        strs.sort(key=key)\n",
    "\n",
    "        return ''.join(strs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password):\n",
    "        # 比较相邻字符串，相互拼接后，转为十进制比较大小，进而交换位置。\n",
    "        # 外层循环n次， 每层循环结束后，都将本次循环中最大的字符串排在最后面\n",
    "        nums=[str(num) for num in password]\n",
    "        print(nums)\n",
    "        n=len(nums)\n",
    "        for j in range(n):\n",
    "            for i in range(n-j-1):\n",
    "                #  15 ， 8 ---- > '15', '8' ---- > '15'+'8'('158')比较'8'+'15'('815')\n",
    "                if int(nums[i]+nums[i+1])>int(nums[i+1]+nums[i]):\n",
    "                    nums[i],nums[i+1]=nums[i+1],nums[i]\n",
    "        print(nums)\n",
    "        return ''.join(map(str,nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        def merge_sort(arr):\n",
    "            if len(arr) < 2:\n",
    "                return arr\n",
    "            mid = len(arr) // 2\n",
    "            return merge(merge_sort(arr[:mid]), merge_sort(arr[mid:]))\n",
    "\n",
    "        def merge(l, r):\n",
    "            res = []\n",
    "            i, j = 0, 0\n",
    "\n",
    "            while i < len(l) and j < len(r):\n",
    "                if str(l[i]) + str(r[j]) > str(r[j]) + str(l[i]):\n",
    "                    # j should be ahead of i\n",
    "                    res.append(r[j])\n",
    "                    j += 1\n",
    "                else:   \n",
    "                    # i should be ahead\n",
    "                    res.append(l[i])\n",
    "                    i += 1\n",
    "            res.extend(l[i:])\n",
    "            res.extend(r[j:])\n",
    "            return res\n",
    "        res = merge_sort(password)\n",
    "        return \"\".join(str(x) for x in res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        def sort_rule(x, y):\n",
    "            a, b = x + y, y + x\n",
    "            if a > b: return 1\n",
    "            elif a < b: return -1\n",
    "            else: return 0\n",
    "        strs = [str(num) for num in password]\n",
    "        print(strs)\n",
    "        strs.sort(key = functools.cmp_to_key(sort_rule))\n",
    "        return ''.join(strs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        def cmp(x, y):\n",
    "            a, b = x+y, y+x\n",
    "            if a > b:\n",
    "                return 1\n",
    "            elif a < b:\n",
    "                return -1\n",
    "            else:\n",
    "                return 0\n",
    "        \n",
    "        a = list(map(str, password))\n",
    "        a.sort(key=functools.cmp_to_key(cmp))\n",
    "        return ''.join(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password):\n",
    "        nums=[str(num) for num in password]\n",
    "        print(nums)\n",
    "        n=len(nums)\n",
    "        for j in range(n):\n",
    "            for i in range(n-j-1):\n",
    "                if int(nums[i]+nums[i+1])>int(nums[i+1]+nums[i]):\n",
    "                    nums[i],nums[i+1]=nums[i+1],nums[i]\n",
    "        print(nums)\n",
    "        return ''.join(map(str,nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compare_func(self, x, y):\n",
    "        return int(str(x) + str(y)) - int(str(y) + str(x))\n",
    "\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        password.sort(key=cmp_to_key(self.compare_func))\n",
    "        password_str = [str(p) for p in password]\n",
    "        return \"\".join(password_str)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        def cmp(x,y):\n",
    "            if x+y==y+x:\n",
    "                return 0\n",
    "            elif x+y>y+x:\n",
    "                return 1\n",
    "            else:\n",
    "                return -1\n",
    "        arr = [str(x) for x in password]\n",
    "        arr.sort(key=functools.cmp_to_key(cmp))\n",
    "        return ''.join(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        return \"\".join(\n",
    "            [str(i) for i in self.quickSort(password)]\n",
    "        )\n",
    "\n",
    "    def quickSort(self, arr: List[int]):\n",
    "        if len(arr) <= 1:\n",
    "            return arr\n",
    "        i,j = 0,len(arr)-1\n",
    "        while i<=j:\n",
    "            if self.cmp(arr[0], arr[i]):\n",
    "                i += 1\n",
    "            else:\n",
    "                arr[i],arr[j] = arr[j],arr[i]\n",
    "                j -= 1\n",
    "        arr[0],arr[j] = arr[j],arr[0]\n",
    "        return self.quickSort(arr[:j]) + [arr[j]] + self.quickSort(arr[j+1:])\n",
    "\n",
    "    def cmp(self, i1: int, i2: int) -> bool:\n",
    "        s1 = str(i1)\n",
    "        s2 = str(i2)\n",
    "        if len(s1) == len(s2):\n",
    "            return i1 >= i2\n",
    "        return int(s1+s2) >= int(s2+s1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        def quick_sort(l , r):\n",
    "            if l >= r: return\n",
    "            i, j = l, r\n",
    "            while i < j:\n",
    "                while strs[j] + strs[l] >= strs[l] + strs[j] and i < j: j -= 1\n",
    "                while strs[i] + strs[l] <= strs[l] + strs[i] and i < j: i += 1\n",
    "                strs[i], strs[j] = strs[j], strs[i]\n",
    "            strs[i], strs[l] = strs[l], strs[i]\n",
    "            quick_sort(l, i - 1)\n",
    "            quick_sort(i + 1, r)\n",
    "        \n",
    "        strs = [str(num) for num in password]\n",
    "        quick_sort(0, len(strs) - 1)\n",
    "        return ''.join(strs)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        def quick_sort(l , r):\n",
    "            if l >= r: return\n",
    "            i, j = l, r\n",
    "            while i < j:\n",
    "                while strs[j] + strs[l] >= strs[l] + strs[j] and i < j: j -= 1\n",
    "                while strs[i] + strs[l] <= strs[l] + strs[i] and i < j: i += 1\n",
    "                strs[i], strs[j] = strs[j], strs[i]\n",
    "            strs[i], strs[l] = strs[l], strs[i]\n",
    "            quick_sort(l, i - 1)\n",
    "            quick_sort(i + 1, r)\n",
    "        \n",
    "        strs = [str(num) for num in password]\n",
    "        quick_sort(0, len(strs) - 1)\n",
    "        return ''.join(strs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        def quickSort(strs, low, high):\n",
    "            if low >= high: return\n",
    "            l, r = low, high\n",
    "            while l < r:\n",
    "                while l < r and strs[low]+strs[r] <= strs[r]+strs[low]: r -= 1\n",
    "                while l < r and strs[low]+strs[l] >= strs[l]+strs[low]: l += 1\n",
    "                strs[l], strs[r] = strs[r], strs[l]\n",
    "            strs[low], strs[l] = strs[l], strs[low]\n",
    "            quickSort(strs, low, l-1)\n",
    "            quickSort(strs, l+1, high)\n",
    "            \n",
    "        strs = [str(num) for num in password]\n",
    "        quickSort(strs, 0, len(strs)-1)\n",
    "        return \"\".join(strs)\n",
    "\n",
    "   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        def quick_sort(left,right):\n",
    "            if left>=right:\n",
    "                return\n",
    "            i,j=left,right\n",
    "            while i<j:\n",
    "                while i<j and strs[left]+strs[j]<=strs[j]+strs[left]:j-=1\n",
    "                while i<j and strs[i]+strs[left]<=strs[left]+strs[i]:i+=1\n",
    "                strs[i],strs[j]=strs[j],strs[i]\n",
    "            strs[left],strs[i]=strs[i],strs[left]\n",
    "            quick_sort(left,i-1)\n",
    "            quick_sort(i+1,right)\n",
    "\n",
    "        strs=[str(num) for num in password]\n",
    "        quick_sort(0,len(strs)-1)\n",
    "        return ''.join(strs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        # lists=str(password)\n",
    "        # print(lists)\n",
    "        # strs=''\n",
    "        # for i in range(len(password)) :\n",
    "        #     password[i]=str(password[i])\n",
    "        # print(password)\n",
    "        # password.sort()\n",
    "        # print(password)\n",
    "        # 统计前面位相同，且长度短的\n",
    "        def quick_sort(l , r):\n",
    "            if l >= r: return\n",
    "            i, j = l, r\n",
    "            while i < j:\n",
    "                while strs[j] + strs[l] >= strs[l] + strs[j] and i < j: j -= 1\n",
    "                while strs[i] + strs[l] <= strs[l] + strs[i] and i < j: i += 1\n",
    "                strs[i], strs[j] = strs[j], strs[i]\n",
    "            strs[i], strs[l] = strs[l], strs[i]\n",
    "            quick_sort(l, i - 1)\n",
    "            quick_sort(i + 1, r)  \n",
    "        strs = [str(num) for num in password]\n",
    "        quick_sort(0, len(strs) - 1)\n",
    "        return ''.join(strs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        def quick_sort(l,r):\n",
    "            if l>=r:\n",
    "                return \n",
    "            i=l \n",
    "            j=r \n",
    "            while i<j:\n",
    "                while strs[j]+strs[l]>=strs[l]+strs[j] and i<j:\n",
    "                    j-=1\n",
    "                while strs[i]+strs[l]<=strs[l]+strs[i] and i<j:\n",
    "                    i+=1\n",
    "                \n",
    "                strs[i],strs[j]=strs[j],strs[i]\n",
    "            #快速排序选择的是第一个元素，所以在找到所有小于第一元素，大于第一个元素的之后需要将第一个元素移动到相应的为止\n",
    "            strs[l],strs[i]=strs[i],strs[l]\n",
    "            quick_sort(l,i-1)\n",
    "            quick_sort(i+1,r)\n",
    "        strs=[str(x) for x in password]\n",
    "        quick_sort(0,len(strs)-1)\n",
    "        return ''.join(strs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        def sort_rule(l, r):\n",
    "            if l >= r : return\n",
    "            i, j = l, r \n",
    "            while i < j :\n",
    "                while strs[j] + strs[l] >= strs[l] + strs[j] and i < j : j -= 1\n",
    "                while strs[i] + strs[l] <= strs[l] + strs[i] and i < j : i += 1\n",
    "                strs[i], strs[j] = strs[j], strs[i]\n",
    "            strs[i], strs[l] = strs[l], strs[i]\n",
    "            sort_rule(l, i-1)\n",
    "            sort_rule(i+1, r)\n",
    "\n",
    "        strs = [str(num) for num in password]\n",
    "        sort_rule(0, len(strs)-1)\n",
    "        return ''.join(strs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        strs = [str(i) for i in password]\n",
    "        left = 0\n",
    "        right = len(password)-1\n",
    "        def quick_sort(left, right):\n",
    "            if right<=left:\n",
    "                return\n",
    "            l, r = left, right\n",
    "            while l<r:\n",
    "                while strs[l]+strs[right]<=strs[right]+strs[l] and l<r :\n",
    "                    l +=1\n",
    "                while strs[r]+strs[right]>=strs[right]+strs[r] and l<r:\n",
    "                    r -=1\n",
    "                strs[l], strs[r] = strs[r], strs[l]  \n",
    "            strs[r] , strs[right] = strs[right], strs[r]\n",
    "            quick_sort(left, r-1)\n",
    "            quick_sort(r+1, right)   \n",
    "        quick_sort(left, right)    \n",
    "        res = ''.join(strs)\n",
    "        return res       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        def keys(x, y):\n",
    "            l = min(len(x), len(y))\n",
    "            for i in range(l):\n",
    "                if ord(x[i]) < ord(y[i]): return True\n",
    "                elif ord(x[i]) > ord(y[i]): return False\n",
    "            if len(y) > len(x):\n",
    "                return keys(x, y[len(x):])\n",
    "            if len(x) > len(y):\n",
    "                return keys(x[len(y):], y)\n",
    "            return True\n",
    "        def qs(ls, l, r):\n",
    "            if l >= r: return\n",
    "            pivot = l\n",
    "            index = l+1\n",
    "            for i in range(index, r+1):\n",
    "                if keys(ls[i], ls[pivot]):\n",
    "                    ls[index], ls[i] = ls[i], ls[index]\n",
    "                    index += 1\n",
    "            ls[index-1], ls[pivot] = ls[pivot], ls[index - 1]\n",
    "            qs(ls, l, index - 2)\n",
    "            qs(ls, index, r)\n",
    "        password = [str(each) for each in password]\n",
    "        qs(password, 0, len(password)-1)\n",
    "        return ''.join(password)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "\n",
    "\n",
    "        # 结果的总位数 <= 所有非负整数位数 （去掉0）\n",
    "\n",
    "        # 0应该靠前\n",
    "        # 每次选择最小的开头，其次比较大小\n",
    "        def quick_sort(l, r):\n",
    "\n",
    "            if l >= r: return \n",
    "\n",
    "            i, j = l, r\n",
    "            while i < j:\n",
    "                while strs[j] + strs[l] >= strs[l] + strs[j] and i < j: j -= 1\n",
    "                while strs[i] + strs[l] <= strs[l] + strs[i] and i < j: i += 1\n",
    "                strs[i], strs[j] = strs[j], strs[i]\n",
    "\n",
    "            strs[i], strs[l] = strs[l], strs[i]\n",
    "            quick_sort(l, i - 1)\n",
    "            quick_sort(i + 1, r)\n",
    "\n",
    "        strs = [str(num) for num in password]\n",
    "        quick_sort(0, len(strs) - 1)\n",
    "        return \"\".join(strs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        def quick_sort(l , r):\n",
    "            if l >= r: return\n",
    "            i, j = l, r\n",
    "            while i < j:\n",
    "                while strs[j] + strs[l] >= strs[l] + strs[j] and i < j: j -= 1\n",
    "                while strs[i] + strs[l] <= strs[l] + strs[i] and i < j: i += 1\n",
    "                strs[i], strs[j] = strs[j], strs[i]\n",
    "            strs[i], strs[l] = strs[l], strs[i]\n",
    "            quick_sort(l, i - 1)\n",
    "            quick_sort(i + 1, r)\n",
    "        \n",
    "        strs = [str(num) for num in password]\n",
    "        quick_sort(0, len(strs) - 1)\n",
    "        return ''.join(strs)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "\n",
    "        strs = [str(password[i]) for i in range(len(password))]\n",
    "\n",
    "        def quick_sort(l, r):\n",
    "            if l>=r:\n",
    "                return\n",
    "            i, j = l, r\n",
    "\n",
    "            while(i < j):\n",
    "                while strs[j] + strs[l] >= strs[l] + strs[j] and j > i: \n",
    "                    j -= 1\n",
    "                while strs[i] + strs[l] <= strs[l] + strs[i] and i < j:\n",
    "                    i += 1\n",
    "                if i != j:\n",
    "                    strs[i], strs[j] = strs[j], strs[i]\n",
    "\n",
    "            strs[l], strs[i] = strs[i], strs[l]\n",
    "\n",
    "            quick_sort(l, i-1)\n",
    "            quick_sort(i+1, r)\n",
    "\n",
    "            return\n",
    "        \n",
    "        quick_sort(0, len(strs)-1)\n",
    "        return ''.join(strs)\n",
    "\n",
    "\n",
    "            \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "from heapq import *\n",
    "from sys import *\n",
    "from itertools import *\n",
    "from functools import *\n",
    "from string import *\n",
    "from bisect import *\n",
    "from graphlib import *\n",
    "from sortedcontainers import *\n",
    "from copy import *\n",
    "\n",
    "class cmpSmaller(str):\n",
    "    def __lt__(self, y):\n",
    "        return self + y < y + self  # 字符串拼接比较(两两比较)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        password = list(map(str, password))\n",
    "        password.sort(key=cmpSmaller)\n",
    "        return \"\".join(password)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        strs = [str(val) for val in password]\n",
    "        def quick_sort(l, r):\n",
    "            if l >= r: return \n",
    "            i, j = l, r\n",
    "            while i < j:\n",
    "                while strs[j] + strs[l] >= strs[l] + strs[j] and i < j: j -= 1\n",
    "                while strs[i] + strs[l] <= strs[l] + strs[i] and i < j: i += 1\n",
    "                strs[i], strs[j] = strs[j], strs[i]\n",
    "            strs[i], strs[l] = strs[l], strs[i]\n",
    "            quick_sort(l, i - 1)\n",
    "            quick_sort(i + 1, r)\n",
    "        quick_sort(0, len(password) - 1)\n",
    "        return ''.join(strs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        def quick_sort(l, r):\n",
    "            if l >= r: return\n",
    "            i, j = l, r\n",
    "            while i < j:\n",
    "                while strs[j] + strs[l] >= strs[l] + strs[j] and i < j: j -= 1\n",
    "                while strs[i] + strs[l] <= strs[l] + strs[i] and i < j: i += 1\n",
    "                strs[i], strs[j] = strs[j], strs[i]\n",
    "            strs[i], strs[l] = strs[l], strs[i]\n",
    "            quick_sort(l, i - 1)\n",
    "            quick_sort(i + 1, r)\n",
    "        \n",
    "        strs = [str(pw) for pw in password]\n",
    "        quick_sort(0, len(strs) - 1)\n",
    "        return ''.join(strs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "\n",
    "\n",
    "\n",
    "        def quick_sort(l, r):\n",
    "\n",
    "            if l >= r: return \n",
    "\n",
    "            i, j = l, r\n",
    "            while i < j:\n",
    "                while strs[j] + strs[l] >= strs[l] + strs[j] and i < j: j -= 1\n",
    "                while strs[i] + strs[l] <= strs[l] + strs[i] and i < j: i += 1\n",
    "                strs[i], strs[j] = strs[j], strs[i]\n",
    "\n",
    "            strs[i], strs[l] = strs[l], strs[i]\n",
    "            quick_sort(l, i - 1)\n",
    "            quick_sort(i + 1, r)\n",
    "\n",
    "        strs = [str(num) for num in password]\n",
    "        quick_sort(0, len(strs) - 1)\n",
    "        return \"\".join(strs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        def quick_sort(l , r):\n",
    "            if l >= r: return\n",
    "            i, j = l, r\n",
    "            while i < j:\n",
    "                while strs[j] + strs[l] >= strs[l] + strs[j] and i < j: j -= 1\n",
    "                while strs[i] + strs[l] <= strs[l] + strs[i] and i < j: i += 1\n",
    "                strs[i], strs[j] = strs[j], strs[i]\n",
    "            strs[i], strs[l] = strs[l], strs[i]\n",
    "            quick_sort(l, i - 1)\n",
    "            quick_sort(i + 1, r)\n",
    "        \n",
    "        strs = [str(num) for num in password]\n",
    "        quick_sort(0, len(strs) - 1)\n",
    "        return ''.join(strs)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        def quick_sort(l , r):\n",
    "            if l >= r: return\n",
    "            i, j = l, r\n",
    "            while i < j:\n",
    "                while strs[j] + strs[l] >= strs[l] + strs[j] and i < j: j -= 1\n",
    "                while strs[i] + strs[l] <= strs[l] + strs[i] and i < j: i += 1\n",
    "                strs[i], strs[j] = strs[j], strs[i]\n",
    "            strs[j], strs[l] = strs[l], strs[j]\n",
    "            quick_sort(l, i - 1)\n",
    "            quick_sort(i + 1, r)\n",
    "        \n",
    "        strs = [str(num) for num in password]\n",
    "        quick_sort(0, len(strs) - 1)\n",
    "        return ''.join(strs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        if not password:\n",
    "            return \"\"\n",
    "        def quick_sort(l, r):\n",
    "            if l >= r:\n",
    "                return \n",
    "            i, j = l, r\n",
    "            while i < j:\n",
    "                while strs[j] + strs[l] >= strs[l] + strs[j] and i < j:\n",
    "                    j -= 1\n",
    "                while strs[i] + strs[l] <= strs[l] + strs[i] and i < j:\n",
    "                    i += 1\n",
    "                strs[i], strs[j] = strs[j], strs[i]\n",
    "            strs[l], strs[i] = strs[i], strs[l]\n",
    "            quick_sort(l, i-1)\n",
    "            quick_sort(i+1, r)\n",
    "        strs = list(map(str, password))\n",
    "        quick_sort(0, len(strs)-1)\n",
    "        return ''.join(strs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackPassword(self, password: List[int]) -> str:\n",
    "        password = [str(p) for p in password]\n",
    "        def quick_sort(l, r):\n",
    "            if l >= r:\n",
    "                return\n",
    "            i, j = l, r\n",
    "            while i < j:\n",
    "                while password[j] + password[l] >= password[l] + password[j] and i < j:\n",
    "                    j -= 1\n",
    "                while password[i] + password[l] <= password[l] + password[i] and i < j:\n",
    "                    i += 1\n",
    "                password[i], password[j] = password[j], password[i]\n",
    "            password[i], password[l] = password[l], password[i]\n",
    "            quick_sort(l, i - 1)\n",
    "            quick_sort(i + 1, r)\n",
    "        quick_sort(0, len(password) - 1)\n",
    "        return \"\".join(password)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
